import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int useSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    //创建一个大根堆
    public void createHeap(int[] array){
        for (int i =0 ; i < array.length; i++){
            elem[i] = array[i];
            useSize++;
        }//把原始数据 给到了elem数组

        for (int parent = (useSize-1-1)/2 ; parent>=0 ; parent--){
            shiftDown(parent,useSize);
        }
    }

    //parent 每棵子树的根节点
    //len 每棵子树的

    public void shiftDown(int parent,int len){
        int child = 2 * parent +1;
        //是不是一定有左孩子
        while (child < len){
            //一定不会越界！！！
            if (child + 1 < len && elem[child] < elem[child+1]){
                child = child + 1;
            }
            if (elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    public void push(int val){
        //检查满
        if (isFull()){
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        //存数据
        elem[useSize] = val;
        useSize++;
        shiftUp(useSize-1);

    }

    public boolean isFull(){
        return useSize == elem.length;
    }

    //向上调整
    public void shiftUp(int child){
        int parent = ((child-1)/2);
        while (child > 0){
            if (elem[child] > elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else{
                break;
            }
        }
    }

    //删除元素，只能删除堆顶
    public void poll(){
        if (empty()) {
            throw new HeapEmptyException("是空的");
        }
        int tmp = elem[0];
        elem[0] = elem[useSize-1];
        elem[useSize-1] = tmp;
        useSize--;
        shiftDown(0,useSize);

    }

    public boolean empty(){
        return useSize == 0;
    }

    public int peek(){
        if (empty()) {
            throw new HeapEmptyException("是空的");
        }
        return elem[0];
    }


    //1.建立大根堆O(N)+  //可以省略掉
    //2.N*logn
    public void heapSort(){
        int end = useSize - 1;
        while (end > 0){
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end --;
        }
    }
}
